/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */


#ifndef PRIORICODA_H_
#define PRIORICODA_H_

#define NDEBUG
#include <cassert>
#include <iostream>
using namespace std;


template <class T>
class PrioriCoda {
public:
	PrioriCoda();
	PrioriCoda(int);
	~PrioriCoda();

	void creaPrioriCoda();
	void inserisci( T ) throw (char const *);
	T min() throw (char const *);
	void cancellaMin() throw (char const *);

private:
	int MAXLUNG;
	T* heap;
	int ultimo;

	void fixUp();
	void fixDown(int, int);
};

#endif /* PRIORICODA_H_ */




//DEFINIZIONE
template <class T>
PrioriCoda<T>::PrioriCoda():MAXLUNG(100) {
	heap = new T[MAXLUNG];
	creaPrioriCoda ();
}

template <class T>
PrioriCoda<T>::PrioriCoda(int n):MAXLUNG(n) {
	heap = new T[MAXLUNG];
	creaPrioriCoda ();
}

template <class T>
PrioriCoda<T>::~PrioriCoda() {
	delete[] heap;
}


template <class T>
void PrioriCoda<T>::creaPrioriCoda() {
	ultimo = 0;
	for (int i=0;i<MAXLUNG;i++)
		heap[i]=0;
}


template <class T>
void PrioriCoda<T>::inserisci( T e ) throw (char const *) {
	if ( ultimo < MAXLUNG ) {
		heap[ultimo] = e;
		ultimo++;
		fixUp();
	} else
		throw "Lunghezza massima raggiunta;" ;
}


template <class T>
T PrioriCoda<T>::min() throw (char const *) {
	if ( ultimo!=0 )
		return heap[0];
	else
		throw "La coda con priorita' e' vuota." ;
}


template <class T>
void PrioriCoda<T>::cancellaMin() throw (char const *) {
	if ( ultimo!=0 ) {
		heap[0] = heap[ultimo - 1];
		ultimo--;
		fixDown (1,ultimo);
	} else
		throw "La coda con priorita' e' vuota." ;
}

template <class T>
void PrioriCoda<T>::fixUp() {
	int k = ultimo;

	while (k > 1 && heap[ k-1 ] < heap[ k/2-1 ] ) {
		T tmp;
		tmp = heap[k-1];
		heap[k-1] = heap[k/2-1];
		heap[k/2-1] = tmp;
		k = k/2;
	}
}

template <class T>
void PrioriCoda<T>::fixDown(int k, int N) {
	bool scambio = 1;
	int j;

	while (k <= N / 2 && scambio) {
		j = 2 * k;
		T tmp;

		if (j < N && heap[j - 1] > heap[j])
			j++;

		scambio = (heap[j - 1] < heap[k - 1]);
		if (scambio) {
			tmp = heap[k - 1];
			heap[k - 1] = heap[j - 1];
			heap[j - 1] = tmp;
			k = j;
		}
	}
}

